package com.yangzhe.algorithm.c034;

// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
public class Code06_SortList_LeetCode {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode();
        node1.val = 4;

        ListNode node2 = new ListNode();
        node2.val = 2;

        ListNode node3 = new ListNode();
        node3.val = 1;

        ListNode node4 = new ListNode();
        node4.val = 3;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        sortList(node1);
    }

    /**
     * 使用归并排序
     * 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
     * 注意为了额外空间复杂度O(1)，所以不能使用递归
     * 因为mergeSort递归需要O(log n)的额外空间
     *
     * @param head 头节点
     * @return
     */
    public static ListNode sortList(ListNode head) {
        int count = countList(head);
        if (count <= 1) {
            return head;
        }
        // 步长 每次 * 2，让左边有序，右边有序，然后merge
        int step = 1;

        while (step < count) {
            HeadAndEnd left = getNListNode(head, step);
            HeadAndEnd right = getNListNode(left.end.next, step);

            ListNode lastRightNode = right.end.next;
            HeadAndEnd mergeResult = null;
            while (right != null) {
                // 需要记录上一次循环的结果，用于连接链表
                HeadAndEnd lastResult = null;
                if (mergeResult != null) {
                    lastResult = mergeResult;
                }
                mergeResult = merge(left, right);

                if (lastResult != null) {
                    lastResult.end.next = mergeResult.head;
                } else {
                    // 由于链表有头节点，第一次循环的头就作为新的头节点
                    head = mergeResult.head;
                }

                left = getNListNode(lastRightNode, step);
                if (left == null || left.end.next == null) {
                    break;
                }
                right = getNListNode(left.end.next, step);
                lastRightNode = right.end.next;
            }

            step *= 2;
        }

        return head;
    }

    public static HeadAndEnd merge(HeadAndEnd left, HeadAndEnd right) {
        HeadAndEnd headAndEnd = new HeadAndEnd();
        ListNode leftCur = left.head;
        ListNode rightCur = right.head;

        // 处理第一个节点
        ListNode nodeHead;
        if (leftCur.val < rightCur.val) {
            nodeHead = leftCur;
            leftCur = leftCur.next;
        } else {
            nodeHead = rightCur;
            rightCur = rightCur.next;
        }
        headAndEnd.head = nodeHead;

        // 哪边小将哪边连到下一个节点
        ListNode rightRangeNode = right.end.next;
        while (leftCur != right.head && rightCur != rightRangeNode && rightCur != null) {
            if (leftCur.val < rightCur.val) {
                nodeHead.next = leftCur;
                leftCur = leftCur.next;
            } else {
                nodeHead.next = rightCur;
                rightCur = rightCur.next;
            }
            nodeHead = nodeHead.next;
        }

        // 将左边或右边剩余的节点连到链表中
        while (leftCur != right.head) {
            nodeHead.next = leftCur;
            nodeHead = nodeHead.next;
            leftCur = leftCur.next;
        }

        while (rightCur != rightRangeNode && rightCur != null) {
            nodeHead.next = rightCur;
            nodeHead = nodeHead.next;
            rightCur = rightCur.next;
        }

        headAndEnd.end = nodeHead;

        // 将新链表和原链表连接起来
        nodeHead.next = rightRangeNode;

        return headAndEnd;
    }

    /**
     * 计算链表长度
     *
     * @param head 头节点
     * @return 链表长度
     */
    public static int countList(ListNode head) {
        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }

        return count;
    }

    /**
     * 从当前节点向后获取n个节点
     *
     * @param head 头节点
     * @param n    数量
     * @return 头和尾
     */
    public static HeadAndEnd getNListNode(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        HeadAndEnd headAndEnd = new HeadAndEnd();
        headAndEnd.head = head;
        while (head != null && n != 0) {
            headAndEnd.end = head;
            head = head.next;
            n--;
        }

        return headAndEnd;
    }

    public static class HeadAndEnd {
        ListNode head;
        ListNode end;
    }
}
